package com.example.test.算法;

import java.util.Arrays;

public class 快速排序 {

    /**
     * @Description 快速排序 从小到大
     * 选取一个基数,两边i j指针分别动向中间移动,以此与基数比较
     * 当指针i 大于基数,并且j 小于基数,那么二者交换
     * 结束条件为当i=j的时候,一次处理结束,基数找到了,它自己的位置
     * 然后继续进行 0===i-1 和 i+1===长度减一的 处理 相当于递归调用
     * @Author 寂寞旅行
     * @Date 19:20 2022/2/26
     * @Param [args]
     **/
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1, 9, 8, 10};
        quickSort(arr, 0, arr.length - 1);

    }

    private static void quickSort(int[] arr, int i, int j) {
        if (i > j) {
            return;
        }
        int begin = i;
        int jizhun = arr[begin];
        int end = j;
        System.out.println(Arrays.toString(arr));
        while (i != j) {
            while (arr[j] >= jizhun && i < j) {
                j--;
            }
            while (arr[i] <= jizhun && i < j) {
                i++;
            }
            if (j > i) {
                //交换
                int temp;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        arr[begin] = arr[i];
        arr[i] = jizhun;
        quickSort(arr, begin, i - 1);
        quickSort(arr, i + 1, end);

    }

}
